ﻻ يوجد ملخص باللغة العربية
A (not necessarily proper) vertex colouring of a graph has clustering $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $Delta$ are 3-colourable with clustering $O(Delta^2)$. The previous best bound was $O(Delta^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $Delta$ that exclude a fixed minor are 3-colourable with clustering $O(Delta^5)$. The best previous bound for this result was exponential in $Delta$.
A graph $G$ is called $3$-choice critical if $G$ is not $2$-choosable but any proper subgraph is $2$-choosable. A characterization of $3$-choice critical graphs was given by Voigt in [On list Colourings and Choosability of Graphs, Habilitationsschrif
For $kgeq 1$, a $k$-colouring $c$ of $G$ is a mapping from $V(G)$ to ${1,2,ldots,k}$ such that $c(u) eq c(v)$ for any two non-adjacent vertices $u$ and $v$. The $k$-Colouring problem is to decide if a graph $G$ has a $k$-colouring. For a family of gr
Answering some questions of Gutman, we show that, except for four specific trees, every connected graph G of order n, with no cycle of order 4 and with maximum degree at most 3, has energy greater that its order. Here, the energy of a graph is the su
This paper disproves a conjecture of Wang, Wu, Yan and Xie, and answers in negative a question in Dvorak, Pekarek and Sereni. In return, we pose five open problems.
3-list colouring is an NP-complete decision problem. It is hard even on planar bipartite graphs. We give a polynomial-time algorithm for solving 3-list colouring on permutation graphs.