Note: The references are not ordered alphabetically!
1700 |
R.A. Wilson Graphs, colourings and the four-colour theorem Oxford University Press, London 2002 |
1701 |
M. Vatshelle New Width Parameters of Graphs PhD Thesis, Dept. of Informatics, University of Bergen 2012 |
1702 |
M. Sorge, M. Weller The graph parameter hierarchy Manuscript, 2013 Available here. |
1704 | Taking a clique $C$ and each vertex in the complement $V \setminus C$ of $C$ as a singleton yields a clique cover. |
1705 | A vertex set that hits all induced $P_3$'s hits, in particular, all induced $P_4$'s. |
1706 | Since each cluster graph is a cographs also each complement of a cluster graph is. Hence, a deletion set into a complement of a cluster graphs is a deletion set into a cograph. |
1707 | A cograph has diameter at most three. Hence, any graph with a deletion set into a cograph of size $a$ has diameter at most $a + 3$. |
1708 |
Be $f(x) = x+1$ The degree $deg_G$ of all vertices $k$ in the maximum clique is $deg_G(k) = \alpha(G) -1$. Hence $deg_G(k)$ is the smallest possible maximum degree of graph $G$. Be $s$ the identifier for all vertices in $G$, which are not in the maximum clique. $deg_G(s) > deg_G(k) \Rightarrow \alpha(G) \leq \beta(G)$ and $deg_G(s)$ is the maximum degree. $deg_G(s) \leq deg_G(k) \Rightarrow deg_G(k)$ is the maximum degree. It follows by $f$: $\alpha(G) \leq \beta(G)+1 \Leftrightarrow \alpha(G) \leq f(\beta(G)) \Rightarrow \alpha \leq_{G} \beta$. |
1709 | The maximum independent set is always a dominating set. Because every edge $e$ of the graph $G$ has one ending in the maximum independent set, except of $e$ is part of a clique. If $\beta$ is also the minimum Dominating Set, $\beta = \alpha$. If there is a smaller Dominating Set than $\beta$, it implies $\alpha < \beta$.Both together implies $\alpha \leq \beta$. |
1710 | Clearly, any independent set can take at most one vertex out of each clique in a clique cover, establishing that maximum independent sets are at most as large as minimum size clique covers. To see that the gap between these two can be arbitrarily large, recall that that Mycielski's graphs show that the chromatic number of a graph can be arbitrarily large whereas the maximum clique size is a constant. Taking the complements of these graphs shows that the same is true for minimum clique covers and independent sets. |
1711 | Take a longest shortest path $P$. No two vertices $u, v$ on $P$ that are at least four steps apart can be dominated by the same vertex. Otherwise, we could replace these subpath of $P$ induced by $u, v$ by a shortcut over the vertex which dominates them, a contradiction to the fact that $P$ is a shortest path between its endpoints. Hence, any dominating set contains at least $|V(P)|/4$ vertices. |
1712 |
Michael O. Albertson and David M. Berman An Acyclic Analogue To Heawood's Theorem Glasgow Mathematical Journal Vol. 19 (2), 163-166 (1978) doi 10.1017/S001708950000358X |
1713 |
William Duckworth, David F. Manlove, Michele Zito On the approximability of the maximum induced matching problem Journal of Discrete Algorithms Vol. 3, 79-91 (2005) doi 10.1016/j.jda.2004.05.001 |
1714 |
W. Espelage, F. Gurski, E. Wanke How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time Proceedings of the 27th International Workshop on Graph-Theoretic Concepts in Computer Science WG'01, LNCS 2204, 117-128 (2001) |
1715 |
R. Ganian, P. Hlineny, J. Obdrzalek Clique-width: When hard does not mean impossible Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl 404-415 (2011) |
1716 |
F. Gurski A comparison of two approaches for polynomial time algorithms computing basic graph parameters Manuscript 2008 Available on arXiv. |
1717 |
K.S. Booth, C.J. Colbourn Problems polynomially equivalent to graph isomorphism Technical report CS-77-04, Computer science department, University of Waterloo (1979) |
1718 |
M.J. Colbourn, C.J. Colbourn Graph isomorphism and self-complementary graphs SIGACT News 10 Nr. 1:25-29 (1978) |
1719 |
F. R. K. Chung On the Cutwidth and the Topological Bandwidth of a Tree SIAM. J. on Algebraic and Discrete Methods 6 No.2, 268-277 (1983) doi 10.1137/0606026 |
1720 |
P. D. Seymour, R. Thomas Call routing and the ratcatcher Combinatorica 14 No.2, 217-241 (1994) doi 10.1007/BF01215352 |
1721 |
D. R. Lick, A. T. White k-degenerate graphs Canad. J. Math. 22 No.5, 1082-1096 (1970) doi 10.4153/CJM-1970-125-1 |
1722 |
J. Nesetril, P. O. de Mendez Tree-depth, subgraph coloring and homomorphism bounds European Journal of Combinatorics 27 No.6, 1022-1041 (2006) doi 10.1016/j.ejc.2005.01.010 |
1723 |
Sang-il Oum, P. Seymour Approximating clique-width and branch-width Journal of Combinatorial Theory, Series B 96 No.4, 514-528 (2006) doi 10.1016/j.jctb.2005.10.006 |
1724 |
B.-M. Bui-Xuan, J.A. Telle, M. Vatshelle Boolean-width of graphs Theoretical Computer Science Vol. 412 (39), 5187-5204 (2011) |
1725 |
L. Auslander, T.A. Brown, J.W.T. Youngs The Imbedding of Graphs in Manifolds Journal of Mathematics and Mechanics Vol. 12, 565-568 (1962) |
1726 |
P. Z. Chinn, J. Chvátalová, A.K. Dewdney, N.E. Gibbs The bandwidth problem for graphs and matrices—a survey Journal of Graph Theory Vol. 6 (3), 223-254 (1982) |
1727 |
R. Crowston, M. Jones, M. Mnich Max-cut parametrized above the Edwards-Erdős bound Algorithmica Jan. 2014 1-24 (2014) doi 10.1007/s00453-014-9870-z |
1728 |
M. Francis, P. Hell, J. Stacho Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm Submitted (2014) Available on arXiv. |
1729 |
T. Liu Restricted Bipartite Graphs: Comparison and Hardness Results Algorithmic Aspects in Information and Management (AAIM 2014) LNCS 8546, 241-252 (2014) doi 10.1007/978-3-319-07956-1_22 |
1730 |
M. Larsen, J. Propp, D. Ullman The Fractional Chromatic Number of Mycielski's Graphs Journal of Graph Theory Vol. 19 (3), 411-416 (1995) doi 10.1002/jgt.3190190313 |
1731 |
H.L. Bodlaender, C.M.H. de Figueiredo, M. Gutierrez, T. Kloks, R. Niedermeier Simple max-cut for split-indifference graphs and graphs with few P4s Proceedings of 3rd Workshop on experimental and efficient algorithms WEA-04, LNCS 3059 87-99 (2004) doi 10.1007/978-3-540-24838-5_7 |
1732 |
V.B. Le, S.-L. Peng Characterizing and recognizing probe block graphs Theoretical Computer Science 568 97-102 (2015) doi 10.1016/j.tcs.2014.12.014 |
1733 |
M.-S. Chang, L.-J. Hung, T. Kloks, S.-L. Peng Block graph width Theoretical Computer Science 412 2496-2502 (2011) |
1734 |
P. Erdos Graph theory and probability Canadian J. of Math. 11 34-38 (1959) doi 10.4153/CJM-1959-003-9 |
1735 |
E. Wanke k-NLC graphs and polynomial algorithsm Discrete Appl. Math. 54 No.2 251-266 (1994) doi 10.1016/0166-218X(94)90026-4 |
1736 |
F.V. Fomin, P.A. Golovach, D. Lokshtanov, S. Saurabh Almost optimal lower bounds for problems parametrized by clique-width SIAM J. Comput. 43 No.5 1541-1563 (2014) doi 10.1137/130910932 |
1737 |
D. Lokshktanov, M. Pilipczuk, M. Pilipczuk, S. Saurabh Fixed-Parameter-Tractable canonization and isomorphism test for graphs of bounded treewidth 55th IEEE Annual Symposium on Foundations of Computer Science FOCS-2014 186-195 (2014) doi 10.1109/FOCS.2014.28 |
1738 |
C.T. Hoang On the complexity of finding a sun in a graph SIAM J. Discrete Math. 23 No.4 2156-2162 (2010) |
1739 |
P.J. Heawood On the four-color map theorem Quart. J. Pure Math. 29 270-285 (1898) |
1740 |
B. Grünbaum Acyclic colorings of planar graphs Israel J. of Math. 14 No.4 390-408 (1973) |
1741 | Maximum degree 3 graphs are vertex decomposable into two graphs with maximum degree 1, hence into two P_{4} free graphs. (communicated by P. Ochem) |
1742 | The graph consisting of $n$ copies of K_{2,3} is planar. Add a single vertex $v$ that is adjacent to all vertices of degree 2 (hence it is part of $n$ K_{3,3} s). The resulting graph is an apex graph. |
1743 | The graph consisting of $n$ copies of K_{2,3} is planar. Add a single vertex $v$ that is adjacent to all vertices of degree 2 (hence it is part of $n$ K_{3,3} s). The resulting graph is an apex graph. |
1744 | If an odd hole-free graph does not contain a K_{4} or C_{7} , then it is $K_4$-free perfect and therefore 3-colourable. If it does contain a K_{4} or C_{7} , then it is not 3-colourable. Hence, deciding whether an odd hole-free graph is 3-colourable is equivalent to check whether it contains a K_{4} or C_{7} as an induced subgraph. (Communicated by P. Ochem) |
1745 |
J. Balogh, P. Ochem, A. Pluhar On the interval number of special graphs J. of Graph Theory 46 No.4 241-253 (2004) |
1746 |
J. Balogh, P. Ochem, A. Pluhar On the interval number of special graphs J. of Graph Theory 46 No.4 241-253 (2004) |
1747 |
Use the construction from
[1746]
corollary 4. (Communicated by P. Ochem)
J. Balogh, P. Ochem, A. Pluhar
On the interval number of special graphs J. of Graph Theory 46 No.4 241-253 (2004) |
1748 |
F. Bonomo, C.M.H. de Figueiredo, G. Duran, L.N. Grippo, M.D. Safe, J.L. Szwarcfiter On probe 2-clique graphs and probe diamond-free graphs DMTCS 17 No. 1 187-200 (2015) |
1749 |
S. Dantas, L. Faria, C.M.H. de Figueiredo, R.B. Teixeira The generalized split probe problem Elec. Notes in Discrete Math. 44 39-45 (2013) |
1750 |
Let $C$ be a graph class where the maximum independent set (MIS) is bounded by constant $k$. Weighted independent domination
can be solved in $O(n^k)$: There are $O(n^k)$ independent sets and they can be enumerated. Weighted independent dominating set must be IS by definition. So enumerate all IS, check if they are IDS and keep track of the weight. The complexity is $O(n^k)$. (Communicated by G. Guninski) |
1751 | A pseudo-split graph G is either (1,1)-colorable or contains a C_{5} such that removing any vertex in the C_{5} produces a (1,1)-colorable graph. So G is (1,2)-colorable. (Communicated by P. Ochem) |
1752 | A pseudo-split graph $G$ is either (1,1)-colorable or contains a C_{5} such that removing any vertex $v$ from the C_{5} produces a (1,1)-colorable graph. Let $(K,I)$ be a split-partition of $G\setminus v$, with $x,z\in I$ the neighbours of $v$ in the C_{5} and $y_1\dots y_t$ the neighbours of $v$ in $G\setminus C_5$. We can construct a spider representation of the split graph $G\setminus v$ such that for every $x,y_1,..,y_t,z$ there is a point in the representative sets such that these points are consecutive on the circle, and then we add a segment for v. (Communicated by P. Ochem) |
1753 | A pseudo-split graph $G$ is either (1,1)-colorable or contains a C_{5} such that removing any vertex $v$ from the C_{5} produces a (1,1)-colorable graph. Let $(K,I)$ be a split-partition of $G\setminus v$, with $x,z\in I$ the neighbours of $v$ in the C_{5} and $y_1\dots y_t$ the neighbours of $v$ in $G\setminus C_5$. We can construct a spider representation of the split graph $G\setminus v$ such that for every $x,y_1,..,y_t,z$ there is a point in the representative sets such that these points are consecutive on the circle, and then we add a segment for v. (Communicated by P. Ochem) |
1754 |
D. Goncalves, P. Ochem On star and caterpillar arboricity Discrete Math. 309 No.11 3694-3702 doi 10.1016/j.disc.2008.01.041 |
1755 |
J. Nesetril, P. Ossona de Mendez Colorings and homomorphisms of minor closed classes Discrete and Comput. Geometry 25, The Goodman-Pollack Festschrift 651-664 (2003) doi 10.1007/978-3-642-55566-4_29 |
1756 | A path has tree depth $\Theta(log |V|)$, see wikipedia for a short proof. (Communicated by P. Ochem) |
1757 |
bandwidth is unbounded if the class contains connected graphs such that diameter = o(|V|)
[1726]
.
(Communicated by P. Ochem)
P. Z. Chinn, J. Chvátalová, A.K. Dewdney, N.E. Gibbs
The bandwidth problem for graphs and matrices—a survey Journal of Graph Theory Vol. 6 (3), 223-254 (1982) |
1758 |
The gadget in the proof from
[421]
that 3-colourability is NPC can be partitioned into two linear forests; red and black in the drawing.
(Communicated by P. Ochem)
M.R. Garey, D.S. Johnson, L. Stockmeyer
Some simplified \NP--complete graph problems Theor. Comp. Sci. 1 1976 237--267 |
1759 |
The gadget in the proof from
[421]
that 3-colourability is NPC can be partitioned into two graphs of max degree 1; green and blue in the drawing.
(Communicated by P. Ochem)
M.R. Garey, D.S. Johnson, L. Stockmeyer
Some simplified \NP--complete graph problems Theor. Comp. Sci. 1 1976 237--267 |
1760 | triangle-free graphs have unbounded chromatic number. Take a triangle-free graph with arbitrary large chromatic number $k$, then subdivide every edge. The resulting graph is bipartite and has no induced C_{4} or C_{6} . The oriented chromatic number is $k$ and thus the acyclic chromatic number is $\Omega(ln(k))$. Hence bipartite graphs without induced C_{4} ,C_{6} have unbounded acyclic chromatic number. (Communicated by P. Ochem) |
1761 |
In maximal planar graphs, maximum degree, minimum dominating set and diameter are unbounded. Proof: Maximum degree is unbounded: Every planar graph can be completed into a maximal planar graph by edge addition and maximum degree is unbounded on planar graphs. Proof: minimum dominating set and diameter are unbounded. Take a large triangular grid, complete it into a maximal planar graph. You get graphs with arbitrarily large diameter and thus arbitrarily large minimum dominating set. (Communicated by P. Dorbec) |
1762 |
J. Diaz, G.B. Mertzios Minimum bisection is NP-hard on unit disk graphs Mathematical Foundations of Computer Science 2014, LNCS 8635 251-262 (2014) doi 10.1007/978-3-662-44465-8_22 |
1763 |
M. Grohe, P. Schweitzer Isomorphism Testing for Graphs of Bounded Rank Width Proc. of 55th Annual IEEE Symposium on Foundations of Computer Science FOCS (2015) |
1764 |
V.B. Le, R. Nevries Complexity and algorithms for recognizing polar and monopolar graphs Theoretical Computer Science 528 1-11 (2014) doi 10.1016/j.tcs.2014.01.032 |
1765 |
A. Farrugia Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard Electron. J. Combin. 11 (2004) #R46 |
1766 |
R.I. Tyshkevich, A.A. Chernyak Algorithms for the canonical decomposition of a graph and recognizing polarity Izvestia Akad. Nauk BSSR, Ser. Fiz. Mat. Nauk 6 16–23 (1985) (in Russian) |
1767 |
T. Ekim, P. Hell, J. Stacho, D. de Werra Polarity of chordal graphs Discrete Applied Mathematics 156 No. 13 2469-2479 (2008) doi 10.1016/j.dam.2008.01.026 |
1768 |
R. Churchley, J. Huang On the polarity and monopolarity of graphs J. Graph Theory 76 No. 2 1138-148 (2014) doi 10.1002/jgt.21755 |
1769 |
T. Ekim, P. Heggernes, D. Meister Polar permutation graphs are polynomial-time recognisable European J. Combin. 34 No.3 576-592 (2013) doi 10.1002/jgt.21755 |
1770 |
R. Churchley, J. Huang Line-polar graphs: Characterization and recognition SIAM J. Discrete Math. 25 1269-1284 (2011) |
1771 |
T. Ekim, N.V.R. Mahadev, D. de Werra Polar cographs Discrete Applied Math. 156 No.10 1652-1660 (2008) doi 10.1016/j.dam.2007.08.025 Corrigendum in Discrete Appl. Math. 171 p.158 (2014) |
1772 |
A. Takaoka Graph Isomorphism Completeness for Trapezoid Graphs IEICE Trans. Fundamentals Vol.E98-A No.8 1838-1840 (2015) doi 10.1587/transfun.E98.A.1838 Available on arXiv. |
1773 |
A.R. Curtis, M.C. Lin, R.M. McConnell, Y. Nussbaum, F.J. Soulignac, J.P. Spinrad, J.L. Szwarcfiter Isomorphism of graph classes related to the circular-ones property DMTCS 15 No. 1 157-182 (2013) |
1774 |
T. Calamoneri, B. Sinaimeri Pairwise compatibility graphs: A survey Accepted for SIAM Review Available here. |
1775 |
R. Behr, V. Sivaraman, T. Zaslavsky Mock threshold graphs Available on arXiv. |
1776 |
P. Berman, M. Karpinski On some tighter inapproximability results Proceedings of ICALP 2002, LNCS 1644 200-209 (2002) |
1777 |
M. Yannakakis Embedding planar graph in four pages Journal of Computer and System Sciences 38 36-67 (1989) doi 10.1016/0022-0000(89)90032-9 |
1778 |
F. Bernhart, P.C. Kainen The book thickness of a graph J. of Combin. Th. (B) 27 320-331 (1979) doi 10.1016/0095-8956(79)90021-2 |
1779 |
V. Dujmovic, D.R. Wood Graph treewidth and geometric thickness parameters Discrete and Computational Geometry 37 No.4 641-670 (2007) doi 10.1007/s00454-007-1318-7 |
1780 |
S.M. Malitz Genus g graphs have pagenumber O(√g) J. of Algorithms 17 No.1 85-109 (1994) doi 10.1006/jagm.1994.1028 |
1781 |
E. Di Giacomo, G. Liotta The Hamiltonian augmentation problem and its applications to graph drawing Proc. of WALCOM 2010, LNCS 5942 35-46 (2010) doi 10.1007/978-3-642-11440-3_4 |
1782 |
P.C. Kainen, S. Overbay Book embeddings of graphs and a theorem of Whitney Tech. Report GUGU-2/25/03 Available here. |
1783 |
G. Cornuejols, D. Nadded, W.R. Pulleyblank Halin graphs and the travellings salesman problem Mathematical Programming 26 No.3 287-294 (1983) doi 10.1007/BF02591867 |
1784 | https://en.wikipedia.org/wiki/Subhamiltonian_graph |
1785 |
V.E. Alekseev On lower layers of a lattice of hereditary classes of graphs Diskretn. Anal. Issled. Oper. Ser. 1 4:1 3-12 (1997) |
1786 |
E.R. Scheinerman, J. Zito On the size of hereditary classes of graphs J. Combin. Th. B Vol. 61 No.1 16-39 (1994) |
1787 |
J. Balogh, B. Bollobas, D. Weinreich The speed of hereditary properties of graphs J. Combin. Th. B Vol. 79 No.2 131-156 (2000) |