Search

A class ${\cal G}$ of graphs is $\chi$-{\em polydet} if ${\cal G}$ has a polynomial binding function $f$ and there is a polynomial time algorithm to determine an $f(\omega(G))$-coloring of $G\in {\cal G}$. Let $P_t$ and $C_t$ denote a path and a cycle on $t$ vertices, respectively. A {\em bull} consists of a triangle with two disjoint pendant edges, a {\em hammer} is obtained by identifying an end of $P_3$ with a vertex of a triangle, a {\em fork$^+$} is obtained from $K_{1, 3}$ by subdividing an edge twice. Let $H$ be a bull or a hammer, and $F$ be a $P_7$ or a fork$^+$. We determine all $(C_3, C_4, F)$-free graphs without clique cutsets and universal cliques, and present a close relation between $(C_4, F, H)$-free graphs and the Petersen graph. As a consequence, we show that the classes of $(C_4, F, H)$-free graphs are $\chi$-polydet with nearly optimal linear binding functions.

We use $P_t$ and $C_t$ to denote a path and a cycle on $t$ vertices, respectively. A {\em bull} is a graph consisting of a triangle with two disjoint pendant edges, a {\em hammer} is a graph obtained by identifying an endvertex of a $P_3$ with a vertex of a triangle. A class ${\cal F}$ is $\chi$-bounded if there is a function $f$ such that $\chi(G)\leq f(\omega(G))$ for all induced subgraphs $G$ of a graph in ${\cal F}$. A class ${\cal C}$ of graphs is {\em Pollyanna} (resp. {\em linear-Pollyanna}) if ${\cal C}\cap {\cal F}$ is polynomially (resp. linear-polynomially) $\chi$-bounded for every $\chi$-bounded class ${\cal F}$ of graphs. Chudnovsky {\em et al} \cite{CCDO2023} showed that both the classes of bull-free graphs and hammer-free graphs are Pollyannas. Let $G$ be a connected graph with no clique cutsets and no universal cliques. In this paper, we show that $G$ is $(C_4$, hammer)-free if and only if it has girth at least 5, and $G$ is $(C_4$, bull)-free if and only if it is a clique blowup of some graph of girth at least 5. As a consequence, we show that both the classes of $(C_4$, bull)-free graphs and $(C_4$, hammer)-free graphs are linear-Pollyannas., Comment: 11

Let $G$ and $H$ be two vertex disjoint graphs. The {\em union} $G\cup H$ is the graph with $V(G\cup H)=V(G)\cup (H)$ and $E(G\cup H)=E(G)\cup E(H)$. The {\em join} $G+H$ is the graph with $V(G+H)=V(G)+V(H)$ and $E(G+H)=E(G)\cup E(H)\cup\{xy\;|\; x\in V(G), y\in V(H)$$\}$. We use $P_k$ to denote a {\em path} on $k$ vertices, use {\em fork} to denote the graph obtained from $K_{1,3}$ by subdividing an edge once, and use {\em crown} to denote the graph $K_1+K_{1,3}$. In this paper, we show that (\romannumeral 1) $\chi(G)\le\frac{3}{2}(\omega^2(G)-\omega(G))$ if $G$ is (crown, $P_5$)-free, (\romannumeral 2) $\chi(G)\le\frac{1}{2}(\omega^2(G)+\omega(G))$ if $G$ is (crown, fork)-free, and (\romannumeral 3) $\chi(G)\le\frac{1}{2}\omega^2(G)+\frac{3}{2}\omega(G)+1$ if $G$ is (crown, $P_3\cup P_2$)-free., Comment: arXiv admin note: text overlap with arXiv:2302.06800

Let $P_t$ and $C_t$ be a path and a cycle on $t$ vertices, respectively. In 2021, Choudum {\em et al.} [Disc. Math. 344 (2021) 112244] determined the structures of $(P_7,C_7,C_4$, diamond)-free and $(P_7,C_7,C_4$, gem)-frees, and gave correspondingly tight upper bounds to the chromatic numbers of these graphs. In this paper, we study the structure of $(P_7, C_5$, kite, paraglider)-free graphs, which is a superfamily of $(P_7, C_5$, diamond)-free graphs. We show that there is a unique connected imperfect $(P_7, C_5$, kite, paraglider)-free graph with $\delta(G)\geq\omega(G)+1$, which has no clique cutsets, no universal cliques, and no pair of vertices of which one's neighborhoods contains the other's. As a consequence, we show that $(P_7, C_5$, kite, paraglider)-free graphs are $\chi$-polydet with a binding function $\omega(G)+1$. Where a {\em diamond} (resp. {\em gem}) consists of a $P_3$ (resp. $P_4$) and a new vertex adjacent to all vertices of the $P_3$ (resp. $P_4$), a {\em kite} consists of a $P_4$ and a new vertex adjacent to consecutive three vertices of the $P_4$, and a {\em paraglider} consists of a $C_4$ and a new vertex adjacent to three vertices of the $C_4$.

Let $G$ be a graph. We use $P_t$ and $C_t$ to denote a path and a cycle on $t$ vertices, respectively. A {\em diamond} is a graph obtained from two triangles that share exactly one edge. A {\em kite} is a graph consists of a diamond and another vertex adjacent to a vertex of degree 2 of the diamond. A {\em gem} is a graph that consists of a $P_4$ plus a vertex adjacent to all vertices of the $P_4$. In this paper, we prove some structural properties to $(P_7, C_4,$ diamond)-free graphs, $(P_7, C_4,$ kite)-free graphs and $(P_7, C_4,$ gem)-free graphs. As their corollaries, we show that (\romannumeral 1) $\chi (G)\leq \max\{3,\omega(G)\}$ if $G$ is $(P_7, C_4,$ diamond)-free, (\romannumeral 2) $\chi(G)\leq \omega(G)+1$ if $G$ is $(P_7, C_4,$ kite)-free and (\romannumeral 3) $\chi(G)\leq 2\omega(G)-1$ if $G$ is $(P_7, C_4,$ gem)-free. These conclusions generalize some results of Choudum {\em et al} and Lan {\em et al}.

A $hole$ is an induced cycle of length at least four, and an odd hole is a hole of odd length. A {\em fork} is a graph obtained from $K_{1,3}$ by subdividing an edge once. An {\em odd balloon} is a graph obtained from an odd hole by identifying respectively two consecutive vertices with two leaves of $K_{1, 3}$. A {\em gem} is a graph that consists of a $P_4$ plus a vertex adjacent to all vertices of the $P_4$. A {\em butterfly} is a graph obtained from two traingles by sharing exactly one vertex. A graph $G$ is perfectly divisible if for each induced subgraph $H$ of $G$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $\omega(H[B])<\omega(H)$. In this paper, we show that (odd balloon, fork)-free graphs are perfectly divisible (this generalizes some results of Karthick {\em et al}). As an application, we show that $\chi(G)\le\binom{\omega(G)+1}{2}$ if $G$ is (fork, gem)-free or (fork, butterfly)-free.

A hole is an induced cycle of length at least 4. A graph is called a pentagraph if it has no cycles of length 3 or 4 and has no holes of odd length at least 7, and is called a heptagraph if it has no cycles of length less than 7 and has no holes of odd length at least 9. Let $\l\ge 2$ be an integer. The current authors proved that a graph is 4- colorable if it has no cycles of length less than $2\l+1$ and has no holes of odd length at least $2\l+3$. Confirming a conjecture of Plummer and Zha, Chudnovsky and Seymour proved that every pentagraph is 3-colorable. Following their idea, we show that every heptagraph is 3-colorable.

Let $F_1$ and $F_2$ be two disjoint graphs. The union $F_1\cup F_2$ is a graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)$, and the join $F_1+F_2$ is a graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)\cup \{xy\;|\; x\in V(F_1)\mbox{ and } y\in V(F_2)\}$. In this paper, we present a characterization to $(P_5, K_1\cup K_3)$-free graphs, prove that $\chi(G)\le 2\omega(G)-1$ if $G$ is $(P_5, K_1\cup K_3)$-free. Based on this result, we further prove that $\chi(G)\le $max$\{2\omega(G),15\}$ if $G$ is a $(P_5,K_1+( K_1\cup K_3))$-free graph, and construct an infinite family of $(P_5, K_1+( K_1\cup K_3))$-free graphs such that every graph $G$ in the family satisfies $\chi(G)=2\omega(G)$., Comment: arXiv admin note: text overlap with arXiv:2202.13177

A hole is an induced cycle of length at least 4. Let $\l\ge 2$ be a positive integer, let ${\cal G}_l$ denote the family of graphs which have girth $2\l+1$ and have no holes of odd length at least $2\l+3$, and let $G\in {\cal G}_{\l}$. For a vertex $u\in V(G)$ and a nonempty set $S\subseteq V(G)$, let $d(u, S)=\min\{d(u, v):v\in S\}$, and let $L_i(S)=\{u\in V(G) \mbox{ and } d(u, S)=i\}$ for any integer $i\ge 0$. We show that if $G[S]$ is connected and $G[L_i(S)]$ is bipartite for each $i\in\{1, \ldots, \lfloor{\l\over 2}\rfloor\}$, then $G[L_i(S)]$ is bipartite for each $i>0$, and consequently $\chi(G)\le 4$, where $G[S]$ denotes the subgraph induced by $S$. Let $\theta^-$ be the graph obtained from the Petersen graph by deleting three vertices which induce a path, let $\theta^+$ be the graph obtained from the Petersen graph by deleting two adjacent vertices, and let $\theta$ be the graph obtained from $\theta^+$ by removing an edge incident with two vertices of degree 3. For a graph $G\in{\cal G}_2$, we show that if $G$ is 3-connected and has no unstable 3-cutset then $G$ must induce either $\theta$ or $\theta^-$ but does not induce $\theta^+$. As corollaries, $\chi(G)\le 3$ for every graph $G$ of ${\cal G}_2$ that induces neither $\theta$ nor $\theta^-$, and minimal non-3-colorable graphs of ${\cal G}_2$ induce no $\theta^+$.

Let $G$ be a graph. We say that $G$ is perfectly divisible if for each induced subgraph $H$ of $G$, $V(H)$ can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $\omega(H[B])<\omega(H)$. We use $P_t$ and $C_t$ to denote a path and a cycle on $t$ vertices, respectively. For two disjoint graphs $F_1$ and $F_2$, we use $F_1\cup F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)$, and use $F_1+F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)\cup \{xy\;|\; x\in V(F_1)\mbox{ and } y\in V(F_2)\}$. In this paper, we prove that (i) $(P_5, C_5, K_{2, 3})$-free graphs are perfectly divisible, (ii) $\chi(G)\le 2\omega^2(G)-\omega(G)-3$ if $G$ is $(P_5, K_{2,3})$-free with $\omega(G)\ge 2$, (iii) $\chi(G)\le {3\over 2}(\omega^2(G)-\omega(G))$ if $G$ is $(P_5, K_1+2K_2)$-free, and (iv) $\chi(G)\le 3\omega(G)+11$ if $G$ is $(P_5, K_1+(K_1\cup K_3))$-free.

A hole is an induced cycle of length at least 4, and an odd hole is a hole of odd length. A full house is a graph composed by a vertex adjacent to both ends of an edge in $K_4$ . Let $H$ be the complement of a cycle on 7 vertices. Chudnovsky et al [6] proved that every (odd hole, $K_4$)-free graph is 4-colorable and is 3-colorable if it does not has $H$ as an induced subgraph. In this paper, we use the proving technique of Chudnovsky et al to generalize this conclusion to (odd hole, full house)-free graphs, and prove that for (odd hole, full house)-free graph $G$, $\chi(G)\le \omega(G)+1$, and the equality holds if and only if $\omega(G)=3$ and $G$ has $H$ as an induced subgraph.

We consider the thickness $\theta (G))$ and outerthickness $\theta _o(G)$ of a graph G in terms of its orientable and nonorientable genus. Dean and Hutchinson provided upper bounds for thickness of graphs in terms of their orientable genus. More recently, Concalves proved that the outerthickness of any planar graph is at most 2. In this paper, we apply the method of deleting spanning disks of embeddings to approximate the thickness and outerthickness of graphs. We first obtain better upper bounds for thickness. We then use a similar approach to provide upper bounds for outerthickness of graphs in terms of their orientable and nonorientable genera. Finally we show that the outerthickness of the torus (the maximum outerthickness of all toroidal graphs) is 3. We also show that all graphs embeddable in the double torus have thickness at most 3 and outerthickness at most 5., Comment: 13 pages, one fiugue

Borodin et al figured out a gap of the paper published at J. Combinatorial Theory Ser. B (Vol.96 (2006) 958--963), and gave a new proof with the similar technique. The purpose of this note is to fix the gap by slightly revising the definition of special faces, and adding a few lines of explanation in the proofs (new added text are all in black font)., Comment: 6 pages

An $(L,d)^*$-coloring is a mapping $\phi$ that assigns a color $\phi(v)\in L(v)$ to each vertex $v\in V(G)$ such that at most $d$ neighbors of $v$ receive colore $\phi(v)$. A graph is called $(m,d)^*$-choosable, if $G$ admits an $(L,d)^*$-coloring for every list assignment $L$ with $|L(v)|\geq m$ for all $v\in V(G)$. In this note, it is proved that every toroidal graph, which contains no adjacent triangles and contains no 6-cycles and $l$-cycles for some $l \in \{5,7\}$, is $(3,1)^*$-choosable., Comment: 7 pages