共查询到20条相似文献，搜索用时 0 毫秒
1.
David Défossez 《Journal of Graph Theory》2009,62(2):139-156
In this paper we investigate the problem of clique‐coloring, which consists in coloring the vertices of a graph in such a way that no monochromatic maximal clique appears, and we focus on odd‐hole‐free graphs. On the one hand we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, but on the other hand it is NP‐hard to decide if they are 2‐clique‐colorable, and we do not know if there exists any bound k0 such that they are all k0 ‐clique‐colorable. First we will prove that (odd hole, codiamond)‐free graphs are 2‐clique‐colorable. Then we will demonstrate that the complexity of 2‐clique‐coloring odd‐hole‐free graphs is actually Σ2 P‐complete. Finally we will study the complexity of deciding whether or not a graph and all its subgraphs are 2‐clique‐colorable. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 139–156, 2009 相似文献
2.
David Dfossez 《Journal of Graph Theory》2006,53(3):233-249
We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K4‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006 相似文献
3.
A triangle in a hypergraph is a collection of distinct vertices u, v, w and distinct edges e, f, g with , and . Johansson [Tech. report (1996)] proved that every triangle‐free graph with maximum degree Δ has list chromatic number . Frieze and Mubayi (Electron J Comb 15 (2008), 27) proved that every linear (meaning that every two edges share at most one vertex) triangle‐free triple system with maximum degree Δ has chromatic number . The restriction to linear triple systems was crucial to their proof. We provide a common generalization of both these results for rank 3 hypergraphs (edges have size 2 or 3). Our result removes the linear restriction from 8 , while reducing to the (best possible) result [Johansson, Tech. report (1996)] for graphs. In addition, our result provides a positive answer to a restricted version of a question of Ajtai Erd?s, Komlós, and Szemerédi (combinatorica 1 (1981), 313–317) concerning sparse 3‐uniform hypergraphs. As an application, we prove that if is the collection of 3‐uniform triangles, then the Ramsey number satisfies for some positive constants a and b. The upper bound makes progress towards the recent conjecture of Kostochka, Mubayi, and Verstraëte (J Comb Theory Ser A 120 (2013), 1491–1507) that where C3 is the linear triangle. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 487–519, 2015 相似文献
4.
A finite collection C of k‐sets, where is called a k‐clique if every two k‐sets (called lines) in C have a nonempty intersection and a k‐clique is a called a maximal k‐clique if and C is maximal with respect to this property. That is, every two lines in C have a nonempty intersection and there does not exist A such that , and for all . An elementary example of a maximal k‐clique is furnished by the family of all the k‐subsets of a ‐set. This k‐clique will be called the binomial k‐clique. This paper is intended to give some combinatorial characterizations of the binomial k‐clique as a maximal k‐clique. The techniques developed are then used to provide a large number of examples of mutually nonisomorphic maximal k‐cliques for a fixed value of k. 相似文献
5.
Matthias Kriesell 《Journal of Graph Theory》2017,85(1):207-216
For a graph G, let denote the largest k such that G has k pairwise disjoint pairwise adjacent connected nonempty subgraphs, and let denote the largest k such that G has k pairwise disjoint pairwise adjacent connected subgraphs of size 1 or 2. Hadwiger 's conjecture states that , where is the chromatic number of G. Seymour conjectured for all graphs without antitriangles, that is, three pairwise nonadjacent vertices. Here we concentrate on graphs G with exactly one ‐coloring. We prove generalizations of the following statements: (i) if and G has exactly one ‐coloring then , where the proof does not use the four‐color‐theorem, and (ii) if G has no antitriangles and G has exactly one ‐coloring then . 相似文献
6.
A clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a clique covering is called the local clique cover number of G and is denoted by lcc(G). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well‐known problems are discussed. In particular, it is proved that the local clique cover number of every claw‐free graph is at most , where Δ is the maximum degree of the graph and c is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1–3)(2000), 17–26), we prove that the clique cover number of every connected claw‐free graph on n vertices with the minimum degree δ, is at most , where c is a constant. 相似文献
7.
Hadwiger's conjecture states that every graph with chromatic number χ has a clique minor of size χ. In this paper we prove a weakened version of this conjecture for the class of claw‐free graphs (graphs that do not have a vertex with three pairwise nonadjacent neighbors). Our main result is that a claw‐free graph with chromatic number χ has a clique minor of size $lceilfrac{2}{3}chirceil$. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 259–278, 2010 相似文献
8.
9.
Maria Chudnovsky Chun-Hung Liu Oliver Schaudt Sophie Spirkl Nicolas Trotignon Kristina Vušković 《Journal of Graph Theory》2019,92(2):67-95
We show that triangle-free graphs that do not contain an induced subgraph isomorphic to a subdivision of are 3-colorable. This proves a conjecture of Trotignon and Vušković [J. Graph Theory. 84 (2017), no. 3, pp. 233–248]. 相似文献
10.
11.
Let ${mathcal{H}}=({{X}},{mathcal{E}})Let ${mathcal{H}}=({{X}},{mathcal{E}})$ be a hypergraph with vertex set X and edge set ${mathcal{E}}$. A C‐coloring of ${mathcal{H}}$ is a mapping ?:X→? such that |?(E)|<|E| holds for all edges ${{E}}in{mathcal{E}}$ (i.e. no edge is multicolored). We denote by $bar{chi}({mathcal{H}})$ the maximum number |?(X)| of colors in a C‐coloring. Let further $alpha({mathcal{H}})$ denote the largest cardinality of a vertex set S?X that contains no ${{E}}in{mathcal{E}}$, and $tau({mathcal{H}})=|{{X}}|-alpha({mathcal{H}})$ the minimum cardinality of a vertex set meeting all $E in {mathcal{E}}$. The hypergraph ${mathcal{H}}$ is called C‐perfect if $bar{chi}({mathcal{H}}prime)=alpha({mathcal{H}}prime)$ holds for every induced subhypergraph ${mathcal{H}}primesubseteq{mathcal{H}}$. If ${mathcal{H}}$ is not C‐perfect but all of its proper induced subhypergraphs are, then we say that it is minimally C‐imperfect. We prove that for all r, k∈? there exists a finite upper bound h(r, k) on the number of minimally C‐imperfect hypergraphs ${mathcal{H}}$ with $tau({mathcal{H}})le {{k}}$ and without edges of more than r vertices. We give a characterization of minimally C‐imperfect hypergraphs that have τ=2, which also characterizes implicitly the C‐perfect ones with τ=2. From this result we derive an infinite family of new constructions that are minimally C‐imperfect. A characterization of minimally C‐imperfect circular hypergraphs is presented, too. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 132–149, 2010 相似文献
12.
13.
The smallest number of edges forming an n‐uniform hypergraph which is not r‐colorable is denoted by m(n,r). Erd?s and Lovász conjectured that . The best known lower bound was obtained by Radhakrishnan and Srinivasan in 2000. We present a simple proof of their result. The proof is based on the analysis of a random greedy coloring algorithm investigated by Pluhár in 2009. The proof method extends to the case of r‐coloring, and we show that for any fixed r we have improving the bound of Kostochka from 2004. We also derive analogous bounds on minimum edge degree of an n‐uniform hypergraph that is not r‐colorable. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 407–413, 2015 相似文献
14.
Dmitry A. Shabanov 《Journal of Graph Theory》2011,67(3):226-234
The work is devoted to the calculation of asymptotic value of the choice number of the complete r‐partite graph Km* r = Km, …, m with equal part size m. We obtained the asymptotics in the case lnr = o(lnm). The proof generalizes the classical result of A.L. Rubin for the case r = 2. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 226–234, 2011 67: 226‐234, 2011 相似文献
15.
A tree T is said to be bad, if it is the vertex‐disjoint union of two stars plus an edge joining the center of the first star to an end‐vertex of the second star. A tree T is good, if it is not bad. In this article, we prove a conjecture of Alan Hartman that, for any spanning tree T of K2m, where m ≥ 4, there exists a (2m − 1)‐edge‐coloring of K2m such that all the edges of T receive distinct colors if and only if T is good. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 7–17, 1999 相似文献
16.
A hypergraph is b‐simple if no two distinct edges share more than b vertices. Let m(r, t, g) denote the minimum number of edges in an r‐uniform non‐t‐colorable hypergraph of girth at least g. Erd?s and Lovász proved that A result of Szabó improves the lower bound by a factor of r2?? for sufficiently large r. We improve the lower bound by another factor of r and extend the result to b‐simple hypergraphs. We also get a new lower bound for hypergraphs with a given girth. Our results imply that for fixed b, t, and ? > 0 and sufficiently large r, every r‐uniform b‐simple hypergraph with maximum edge‐degree at most trr1?? is t‐colorable. Some results hold for list coloring, as well. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
17.
Andreas Brandstädt Konrad K. Dabrowski Shenwei Huang Daniël Paulusma 《Journal of Graph Theory》2017,86(1):42-77
A graph is H‐free if it has no induced subgraph isomorphic to H. Brandstädt, Engelfriet, Le, and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique‐width. Brandstädt, Le, and Mosca erroneously claimed that the gem and co‐gem are the only two 1‐vertex P4‐extensions H for which the class of H‐free chordal graphs has bounded clique‐width. In fact we prove that bull‐free chordal and co‐chair‐free chordal graphs have clique‐width at most 3 and 4, respectively. In particular, we find four new classes of H‐free chordal graphs of bounded clique‐width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs H for which the class of H‐free chordal graphs has bounded clique‐width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of ‐free graphs has bounded clique‐width via a reduction to K4‐free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique‐width of H‐free weakly chordal graphs. 相似文献
18.
Gregory J. Puleo 《Journal of Graph Theory》2015,80(1):12-17
Erd?s, Gallai, and Tuza posed the following problem: given an n‐vertex graph G, let denote the smallest size of a set of edges whose deletion makes G triangle‐free, and let denote the largest size of a set of edges containing at most one edge from each triangle of G. Is it always the case that ? We have two main results. We first obtain the upper bound , as a partial result toward the Erd?s–Gallai–Tuza conjecture. We also show that always , where m is the number of edges in G; this bound is sharp in several notable cases. 相似文献
19.
András Pluhár 《Random Structures and Algorithms》2009,35(2):216-221
We give a very short proof of an Erd?s conjecture that the number of edges in a non‐2‐colorable n‐uniform hypergraph is at least f(n)2n, where f(n) goes to infinity. Originally it was solved by József Beck in 1977, showing that f(n) at least clog n. With an ingenious recoloring idea he later proved that f(n) ≥ cn1/3+o(1). Here we prove a weaker bound on f(n), namely f(n) ≥ cn1/4. Instead of recoloring a random coloring, we take the ground set in random order and use a greedy algorithm to color. The same technique works for getting bounds on k‐colorability. It is also possible to combine this idea with the Lovász Local Lemma, reproving some known results for sparse hypergraphs (e.g., the n‐uniform, n‐regular hypergraphs are 2‐colorable if n ≥ 8). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009 相似文献
20.
Let Ωq=Ωq(H) denote the set of proper [q]‐colorings of the hypergraph H. Let Γq be the graph with vertex set Ωq where two colorings σ,τ are adjacent iff the corresponding colorings differ in exactly one vertex. We show that if H=Hn,m;k, k ≥ 2, the random k‐uniform hypergraph with V=[n] and m=dn/k hyperedges then w.h.p. Γq is connected if d is sufficiently large and . This is optimal up to the first order in d. Furthermore, with a few more colors, we find that the diameter of Γq is O(n) w.h.p., where the hidden constant depends on d. So, with this choice of d,q, the natural Glauber dynamics Markov Chain on Ωq is ergodic w.h.p. 相似文献