Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSparse $4$-critical graphs have low circular chromatic number
120
0
0.0
(
0
)
Authors
Benjamin Moore
Ask ChatGPT about the research
No Arabic abstract
Kostochka and Yancey proved that every $4$-critical graph $G$ has $e(G) geq frac{5v(G) - 2}{3}$, and that equality holds if and only if $G$ is $4$-Ore. We show that a question of Postle and Smith-Roberge implies that every $4$-critical graph with no $(7,2)$-circular-colouring has $e(G) geq frac{27v(G) -20}{15}$. We prove that every $4$-critical graph with no $(7,2)$-colouring has $e(G) geq frac{17v(G)}{10}$ unless $G$ is isomorphic to $K_{4}$ or the wheel on six vertices. We also show that if the Gallai Tree of a $4$-critical graph with no $(7,2)$-colouring has every component isomorphic to either an odd cycle, a claw, or a path. In the case that the Gallai Tree contains an odd cycle component, then $G$ is isomorphic to an odd wheel. In general, we show a $k$-critical graph with no $(2k-1,2)$-colouring that contains a clique of size $k-1$ in its Gallai Tree is isomorphic to $K_{k}$.
rate research
Read More
A signed graph is a pair $(G, sigma)$, where $G$ is a graph and $sigma: E(G) to {+, -}$ is a signature which assigns to each edge of $G$ a sign. Various notions of coloring of signed graphs have been studied. In this paper, we extend circular coloring of graphs to signed graphs. Given a signed graph $(G, sigma)$ a circular $r$-coloring of $(G, sigma)$ is an assignment $psi$ of points of a circle of circumference $r$ to the vertices of $G$ such that for every edge $e=uv$ of $G$, if $sigma(e)=+$, then $psi(u)$ and $psi(v)$ have distance at least $1$, and if $sigma(e)=-$, then $psi(v)$ and the antipodal of $psi(u)$ have distance at least $1$. The circular chromatic number $chi_c(G, sigma)$ of a signed graph $(G, sigma)$ is the infimum of those $r$ for which $(G, sigma)$ admits a circular $r$-coloring. For a graph $G$, we define the signed circular chromatic number of $G$ to be $max{chi_c(G, sigma): sigma text{ is a signature of $G$}}$. We study basic properties of circular coloring of signed graphs and develop tools for calculating $chi_c(G, sigma)$. We explore the relation between the circular chromatic number and the signed circular chromatic number of graphs, and present bounds for the signed circular chromatic number of some families of graphs. In particular, we determine the supremum of the signed circular chromatic number of $k$-chromatic graphs of large girth, of simple bipartite planar graphs, $d$-degenerate graphs, simple outerplanar graphs and series-parallel graphs. We construct a signed planar simple graph whose circular chromatic number is $4+frac{2}{3}$. This is based and improves on a signed graph built by Kardos and Narboni as a counterexample to a conjecture of M{a}v{c}ajov{a}, Raspaud, and v{S}koviera.
Let $G$ be a simple graph with maximum degree $Delta(G)$ and chromatic index $chi(G)$. A classic result of Vizing indicates that either $chi(G )=Delta(G)$ or $chi(G )=Delta(G)+1$. The graph $G$ is called $Delta$-critical if $G$ is connected, $chi(G )=Delta(G)+1$ and for any $ein E(G)$, $chi(G-e)=Delta(G)$. Let $G$ be an $n$-vertex $Delta$-critical graph. Vizing conjectured that $alpha(G)$, the independence number of $G$, is at most $frac{n}{2}$. The current best result on this conjecture, shown by Woodall, is that $alpha(G)<frac{3n}{5}$. We show that for any given $varepsilonin (0,1)$, there exist positive constants $d_0(varepsilon)$ and $D_0(varepsilon)$ such that if $G$ is an $n$-vertex $Delta$-critical graph with minimum degree at least $d_0$ and maximum degree at least $D_0$, then $alpha(G)<(frac{{1}}{2}+varepsilon)n$. In particular, we show that if $G$ is an $n$-vertex $Delta$-critical graph with minimum degree at least $d$ and $Delta(G)ge (d+2)^{5d+10}$, then [ alpha(G) < left. begin{cases} frac{7n}{12}, & text{if $d= 3$; } frac{4n}{7}, & text{if $d= 4$; } frac{d+2+sqrt[3]{(d-1)d}}{2d+4+sqrt[3]{(d-1)d}}n<frac{4n}{7}, & text{if $dge 19$. } end{cases} right. ]
A class of simple graphs such as ${cal G}$ is said to be {it odd-girth-closed} if for any positive integer $g$ there exists a graph $G in {cal G}$ such that the odd-girth of $G$ is greater than or equal to $g$. An odd-girth-closed class of graphs ${cal G}$ is said to be {it odd-pentagonal} if there exists a positive integer $g^*$ depending on ${cal G}$ such that any graph $G in {cal G}$ whose odd-girth is greater than $g^*$ admits a homomorphism to the five cycle (i.e. is $C_{_{5}}$-colorable). In this article, we show that finding the odd girth of generalized Petersen graphs can be transformed to an integer programming problem, and using this we explicitly compute the odd girth of such graphs, showing that the class is odd-girth-closed. Also, motivated by showing that the class of generalized Petersen graphs is odd-pentagonal, we study the circular chromatic number of such graphs.
Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.
By a finite type-graph we mean a graph whose set of vertices is the set of all $k$-subsets of $[n]={1,2,ldots, n}$ for some integers $nge kge 1$, and in which two such sets are adjacent if and only if they realise a certain order type specified in advance. Examples of such graphs have been investigated in a great variety of contexts in the literature with particular attention being paid to their chromatic number. In recent joint work with Tomasz {L}uczak, two of the authors embarked on a systematic study of the chromatic numbers of such type-graphs, formulated a general conjecture determining this number up to a multiplicative factor, and proved various results of this kind. In this article we fully prove this conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
