The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Eric Sopena - One of the best experts on this subject based on the ideXlab platform.
-
On the signed Chromatic Number of some classes of graphs
2020Co-Authors: Julien Bensmail, Theo Pierron, Sandip Das, Soumen Nandi, Sagnik Sen, Eric SopenaAbstract:A signed graph $(G, \sigma)$ is a graph $G$ along with a function $\sigma: E(G) \to \{+,-\}$. A closed walk of a signed graph is positive (resp., negative) if it has an even (resp., odd) Number of negative edges, counting repetitions. A homomorphism of a (simple) signed graph to another signed graph is a vertex-mapping that preserves adjacencies and signs of closed walks. The signed Chromatic Number of a signed graph $(G, \sigma)$ is the minimum Number of vertices $|V(H)|$ of a signed graph $(H, \pi)$ to which $(G, \sigma)$ admits a homomorphism. Homomorphisms of signed graphs have been attracting growing attention in the last decades, especially due to their strong connections to the theories of graph coloring and graph minors. These homomorphisms have been particularly studied through the scope of the signed Chromatic Number. In this work, we provide new results and bounds on the signed Chromatic Number of several families of signed graphs (planar graphs, triangle-free planar graphs, $K_n$-minor-free graphs, and bounded-degree graphs).
-
on the maximum average degree and the oriented Chromatic Number of a graph
Discrete Mathematics, 1999Co-Authors: O V Borodin, Jaroslav Nesetřil, Alexandr V Kostochka, Andre Raspaud, Eric SopenaAbstract:Abstract The oriented Chromatic Number o( H ) of an oriented graph H is defined as the minimum order of an oriented graph H ′ such that H has a homomorphism to H ′. The oriented Chromatic Number o( G ) of an undirected graph G is then defined as the maximum oriented Chromatic Number of its orientations. In this paper we study the links between o( G ) and mad( G ) defined as the maximum average degree of the subgraphs of G.
-
The Chromatic Number of oriented graphs
Journal of Graph Theory, 1997Co-Authors: Eric SopenaAbstract:We introduce in this paper the notion of the Chromatic Number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the Chromatic Number of oriented k-trees and of oriented graphs with bounded degree. We show that there exist oriented k-trees with Chromatic Number at least 2k+1 - 1 and that every oriented k-tree has Chromatic Number at most (k + 1) × 2k. For 2-trees and 3-trees we decrease these upper bounds respectively to 7 and 16 and show that these new bounds are tight. As a particular case, we obtain that oriented outerplanar graphs have Chromatic Number at most 7 and that this bound is tight too. We then show that every oriented graph with maximum degree k has Chromatic Number at most (2k - 1) × 22k-2. For oriented graphs with maximum degree 2 we decrease this bound to 5 and show that this new bound is tight. For oriented graphs with maximum degree 3 we decrease this bound to 16 and conjecture that there exists no such connected graph with Chromatic Number greater than 7. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 191–205, 1997
Nicholas C Wormald - One of the best experts on this subject based on the ideXlab platform.
-
on the Chromatic Number of a random 5 regular graph
Journal of Graph Theory, 2009Co-Authors: Josep Diaz, Alexis C Kaporis, Graeme Kemkes, Lefteris M Kirousis, X Perez, Nicholas C WormaldAbstract:It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5-regular graph asymptotically almost surely has Chromatic Number at most 4. Here, we show that the Chromatic Number of a random 5-regular graph is asymptotically almost surely equal to 3, provided a certain four-variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the Number of locally rainbow balanced 3-colorings, where a coloring is balanced if the Number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 157–191, 2009
-
the acyclic edge Chromatic Number of a random d regular graph is d 1
Journal of Graph Theory, 2005Co-Authors: Jaroslav Nesetřil, Nicholas C WormaldAbstract:We prove the theorem from the title: the acyclic edge Chromatic Number of a random d-regular graph is asymptotically almost surely equal to d + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) + 2 is the bound for the acyclic edge Chromatic Number of any graph G. It also represents an analog of a result of Robinson and the second author on edge Chromatic Number. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 69–74, 2005 AMS classification: 05C15 (primary: graph coloring) 68R05 (secondary: combinatorics).
Shakhar Smorodinsky - One of the best experts on this subject based on the ideXlab platform.
-
on the Chromatic Number of some geometric hypergraphs
Symposium on Discrete Algorithms, 2006Co-Authors: Shakhar SmorodinskyAbstract:A finite family R of simple Jordan regions in the plane defines a hypergraph H = H(R) where the vertex set of H is R and the hyperedges are all subsets S ⊂ R for which there is a point p such that S = {r ∈ R|p ∈ r. The Chromatic Number of H(R) is the minimum Number of colors needed to color the members of R such that no hyperedge is monoChromatic. In this paper we initiate the study of the Chromatic Number of such hypergraphs. We obtain the following results:(i) any hypergraph that is induced by a family of n simple Jordan regions (not necessarily convex) such that the union complexity of any m of them is given by u(m) and u(m)/m is non-decreasing is O(u(n)/n)-colorable. Thus, for example we prove that any finite family of pseudodiscs can be colored with a constant Number of colors.(ii) any hypergraph induced by a finite family of planar discs is four-colorable. This bound is tight. In fact, we prove that this statement is equivalent to the Four-Color Theorem.(iii) any hypergraph induced by n axis-parallel rectangles is O(log n)-colorable. This bound is asymptotically tight.Our proofs are constructive. Namely, we provide deterministic polynomial-time algorithms for coloring such hypergraphs with only "few" colors (that is, the Number of colors used by these algorithms is upper bounded by the same bounds we obtain on the Chromatic Number of the given hypergraphs)As an application of (i) and (ii) we obtain simple constructive proofs for the following:(iv) Any set of n Jordan regions with near linear union complexity admits a conflict-free (CF) coloring with polylogarithmic Number of colors.(v) Any set of n axis-parallel rectangles admits a CF-coloring with O(log2(n)) colors.
Frederic Meunier - One of the best experts on this subject based on the ideXlab platform.
-
the Chromatic Number of almost stable kneser hypergraphs
Journal of Combinatorial Theory Series A, 2011Co-Authors: Frederic MeunierAbstract:Let V(n,k,s) be the set of k-subsets S of [n] such that for all i,[email protected]?S, we have |i-j|>=s. We define almost s-stable Kneser hypergraph KG^r([n]k)"s"-"s"t"a"b^~ to be the r-uniform hypergraph whose vertex set is V(n,k,s) and whose edges are the r-tuples of disjoint elements of V(n,k,s). With the help of a Z"p-Tucker lemma, we prove that, for p prime and for any n>=kp, the Chromatic Number of almost 2-stable Kneser hypergraphs KG^p([n]k)"2"-"s"t"a"b^~ is equal to the Chromatic Number of the usual Kneser hypergraphs KG^p([n]k), namely that it is equal to @?n-(k-1)[email protected]?. Related results are also proved, in particular, a short combinatorial proof of [email protected]?s theorem (about the Chromatic Number of stable Kneser graphs) and some evidences are given for a new conjecture concerning the Chromatic Number of usual s-stable r-uniform Kneser hypergraphs.
-
the Chromatic Number of almost stable kneser hypergraphs
arXiv: Combinatorics, 2009Co-Authors: Frederic MeunierAbstract:Let $V(n,k,s)$ be the set of $k$-subsets $S$ of $[n]$ such that for all $i,j\in S$, we have $|i-j|\geq s$ We define almost $s$-stable Kneser hypergraph $KG^r{{[n]}\choose k}_{s{\tiny{\textup{-stab}}}}^{\displaystyle\sim}$ to be the $r$-uniform hypergraph whose vertex set is $V(n,k,s)$ and whose edges are the $r$-uples of disjoint elements of $V(n,k,s)$. With the help of a $Z_p$-Tucker lemma, we prove that, for $p$ prime and for any $n\geq kp$, the Chromatic Number of almost 2-stable Kneser hypergraphs $KG^p {{[n]}\choose k}_{2{\tiny{\textup{-stab}}}}^{\displaystyle\sim}$ is equal to the Chromatic Number of the usual Kneser hypergraphs $KG^p{{[n]}\choose k}$, namely that it is equal to $\lceil\frac{n-(k-1)p}{p-1}\rceil.$ Defining $\mu(r)$ to be the Number of prime divisors of $r$, counted with multiplicities, this result implies that the Chromatic Number of almost $2^{\mu(r)}$-stable Kneser hypergraphs $KG^r{{[n]}\choose k}_{2^{\mu(r)}{\tiny{\textup{-stab}}}}^{\displaystyle\sim}$ is equal to the Chromatic Number of the usual Kneser hypergraphs $KG^r{{[n]}\choose k}$ for any $n\geq kr$, namely that it is equal to $\lceil\frac{n-(k-1)r}{r-1}\rceil.$
Jaroslav Nesetřil - One of the best experts on this subject based on the ideXlab platform.
-
the acyclic edge Chromatic Number of a random d regular graph is d 1
Journal of Graph Theory, 2005Co-Authors: Jaroslav Nesetřil, Nicholas C WormaldAbstract:We prove the theorem from the title: the acyclic edge Chromatic Number of a random d-regular graph is asymptotically almost surely equal to d + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) + 2 is the bound for the acyclic edge Chromatic Number of any graph G. It also represents an analog of a result of Robinson and the second author on edge Chromatic Number. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 69–74, 2005 AMS classification: 05C15 (primary: graph coloring) 68R05 (secondary: combinatorics).
-
on the maximum average degree and the oriented Chromatic Number of a graph
Discrete Mathematics, 1999Co-Authors: O V Borodin, Jaroslav Nesetřil, Alexandr V Kostochka, Andre Raspaud, Eric SopenaAbstract:Abstract The oriented Chromatic Number o( H ) of an oriented graph H is defined as the minimum order of an oriented graph H ′ such that H has a homomorphism to H ′. The oriented Chromatic Number o( G ) of an undirected graph G is then defined as the maximum oriented Chromatic Number of its orientations. In this paper we study the links between o( G ) and mad( G ) defined as the maximum average degree of the subgraphs of G.
