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 P4 free graphs. (communicated by P. Ochem)
1742 The graph consisting of $n$ copies of K2,3 is planar. Add a single vertex $v$ that is adjacent to all vertices of degree 2 (hence it is part of $n$ K3,3 s). The resulting graph is an apex graph.
1743 The graph consisting of $n$ copies of K2,3 is planar. Add a single vertex $v$ that is adjacent to all vertices of degree 2 (hence it is part of $n$ K3,3 s). The resulting graph is an apex graph.
1744 If an odd hole-free graph does not contain a K4 or C7 , then it is $K_4$-free perfect and therefore 3-colourable. If it does contain a K4 or C7 , 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 K4 or C7 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]
J. Balogh, P. Ochem, A. Pluhar
On the interval number of special graphs
J. of Graph Theory 46 No.4 241-253 (2004)
corollary 4. (Communicated by P. Ochem)
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 C5 such that removing any vertex in the C5 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 C5 such that removing any vertex $v$ from the C5 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 C5 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 C5 such that removing any vertex $v$ from the C5 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 C5 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]
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)
. (Communicated by P. Ochem)
1758 The gadget in the proof from
[421]
M.R. Garey, D.S. Johnson, L. Stockmeyer
Some simplified \NP--complete graph problems
Theor. Comp. Sci. 1 1976 237--267
that 3-colourability is NPC can be partitioned into two linear forests; red and black in the drawing. (Communicated by P. Ochem)
1759 The gadget in the proof from
[421]
M.R. Garey, D.S. Johnson, L. Stockmeyer
Some simplified \NP--complete graph problems
Theor. Comp. Sci. 1 1976 237--267
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)
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 C4 or C6 . The oriented chromatic number is $k$ and thus the acyclic chromatic number is $\Omega(ln(k))$. Hence bipartite graphs without induced C4 ,C6 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)
1788 V.E. Alekseev
Range of values of entropy of hereditary classes of graphs
Diskretn. Math. 4:2 148-157 (1995)
1789 B. Bollobas, A. Thomason
Projections of bodies and hereditary properties of hypergraphs
Bull. London Math. Soc. 27(5) 417-424 (1995)
1790 J.P. Spinread
Nonredundant 1s in $\Gamma$-free matrices
SIAM J. on Discrete Math. 8(2) 251-257 (1995)
1791 V.V. Lozin, C. Mayhill, V. Zamaraev
Locally bounded coverings and factorial properties of graphs
European J. Combin. 33 No.4 534-543 (2012)
1792 V. Zamaraev, personal communication
1793 D. Cavallaro
Hamiltonicity and the computational complexity of graph problems
Bachelor Thesis, TU Berlin (2019)
Available here.
1794 H. Fleischner, G. Sabidussi, V.I. Sarvanov
Maximum independent sets in 3- and 4-regular Hamiltonian graphs
Discrete Math. 310 No.20 2742-2749 (2010)
1795 R. Belmonte, M. Vatshelle
On classes of graphs with logarithmic boolean-width
Available on arXiv.
1796 N. Korpelainen, V.V. Lozin, C. Mayhill
Split permutation graphs
Graphs and Combinatorics 30 633-646 (2014)
doi 10.1007/s00373-013-1290-3
1797 R.B. Allan, R. Laskar
On domination and independent domination number of a graph
Discrete Math. 23 No.2 73-76 (1978)
doi 10.1016/0012-365X(78)90105-X
1798 E.M. Eschen, X. Wang
Algorithms for unipolar and generalized split graphs
Discrete Applied Math. 162 195-201 (2014)
doi 10.1016/j.dam.2013.08.011
1799 S. Cabello, J. Cardinal, S. Langerman
The clique problem in ray intersection graphs
Discrete and computational Geom. 50 771-783 (2013)
doi 10.1007/s00454-013-9538-5