Note: The references are not ordered alphabetically!
1500 | K3,3 is a discriminating graph. |
1501 |
G. Duran, M.C. Lin Clique graphs of Helly circular-arc graphs Ars Combin. 60 255-271 (2001) |
1502 |
G. Duran, M.C. Lin On some subclasses of circular-arc graphs Technical Report TR003-99 Departamento de Computacion, FCEyN, Universided de Buenos Aires (1999) |
1503 |
B. Hedman Clique graphs of time graphs J. Combin. Theory Ser. B. 37 (3) 270-278 (1968) |
1504 |
For any graph G, if we add a universal vertex vertex v, G+v is a dually chordal graph. This fact allows a trivial reduction,
since the new vertex increases the chromatic number and the size of the largest clique by exactly 1. (Communicated by Vinicius
Santos) Furthermore, the clique cover number of G and G+v are equal, hence we have a reduction for clique cover, as well. (Communicated by Arne Leitert) |
1505 |
A. Leitert 3-Colourability of dually chordal graphs in linear time Manuscript, 2012 Available on arxiv. |
1506 | For any connected graph G, if we add a universal vertex vertex v, H = G+v is a locally connected graph. This fact allows a trivial reduction, since the new vertex increases the chromatic number and the size of the largest clique by exactly 1. Furthermore, the clique cover number of G and G+v are equal, hence we have a reduction for clique cover, as well. Similarly for independent set. (Communicated by Pavel Irzhavski). Treewidth is reduced analogously to clique (Communicated by Arne Leitert). For the domination problem, we add a true twin to every vertex (V*={v, v* | v in V} and E*={uv, u*v, uv*, u*v* | uv in E}). Then every dominating set in G is also dominating in G* and a minimal dominating set in G* can be converted to a minimal dominating set in G by replacing every vertex v* in the set by v (Communicated by Arne Leitert). |
1507 |
P. Heggernes, P. van 't Hof, D. Lokshtanov, J. Nederlof Computing the cutwidth of bipartite permutation graphs in linear time Proceedings of the 36th international conference on Graph-theoretic concepts in computer science WG 2010 75-87 (2010) Available here. |
1508 |
D.M. Thilikos, M. Serna, H.L. Bodlaender Cutwidth I: a linear time fixed parameter algorithm J. of Algorithms 56 Issue 1 1-24 (2005) |
1509 |
B. Monien, I.H. Sudborough Min cut is NP-complete for edge weighted trees Theoretical Comp. Sci. 58 Issue 1-3, 209-229 (1988) |
1510 |
P. Heggernes, D. Lokshtanov, R. Mihai, C. Papadopoulos Cutwidth of split graphs, threshold graphs, and proper interval graphs Proceedings of WG 2008, LNCS 5344, pp. 218-229 (2008) |
1511 |
J. Diaz, M. Penrose, J. Petit, M. Serna Approximating layout problems on random geometric graphs Journal of Algorithms 39 78-117 (2001) |
1512 |
J. Diaz, J. Petit, M. Serna A survey on graph layout problems ACM Computing surveys 34 313-356 (2002) |
1513 |
J. Yuan, S. Zhou Optimal labelling of unit interval graphs Appl. Math. J. Chinese Univ. Ser. B (English edition) 10 337-344 (1995) |
1514 |
M. Yannakakis A polynomial algorithm for the min cut linear arrangement of trees Journal of ACM Vol 32, 950-988 (1985) |
1515 |
D.M. Thilikos, M. Serna, H.L. Bodlaender Cutwidth II: algorithms for partial w-trees of bounded degree J. of Algorithms 56 Issue 1 25-49 (2005) |
1516 |
H. ElGindy Hierarchical decomposition of polygons with applications Ph.D. Thesis, McGill University (1985) |
1517 |
H. Mueller Hamiltonian circuits in chordal bipartite graphs Discrete Math. 156 291-298 (1996) doi 10.1016/0012-365X(95)00057-4 |
1518 |
P. Damaschke The Hamiltonian circuit problem for circle graphs is NP-complete Information Proc. Lett. 32 No.1 1-2 (1989) doi 10.1016/0020-0190(89)90059-8 |
1519 |
G. Narasimhan A note on the Hamiltonian Circuit Problem on directed path graphs Information Proc. Lett. 32 No.4 167-170 (1989) doi 10.1016/0020-0190(89)90038-0 |
1520 |
A.A. Bertossi, M.A. Bonuccelli Hamiltonian Circuits in interval graph generalizations Information Proc. Lett. 23 195-200 (1986) |
1521 |
A.A. Bertossi The edge Hamiltonian path problem is NP-complete Information Proc. Lett. 13 157-159 (1981) |
1522 |
T.-H. Lai, S.-S. Wei The edge Hamiltonian path problem is NP-complete for bipartite graphs Information Proc. Lett. 46 No.1 21-26 (1993) |
1523 |
T. Akiyama, T. Nishizeki, N. Saito NP-completeness of the Hamiltonian cycle problem for bipartite graphs J. Inf. Process. V.3 73-76 (1980) |
1524 |
J.S. Deogun, G. Steiner Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs SIAM J. Computing 23 Issue 3 520-552 (1994) doi 10.1137/S0097539791200375 |
1525 |
C.J. Colbourn, L.K. Stewart Dominating cycles in series-parallel graphs Ars Combin. 19A 107-112 (1985) |
1526 |
B.S. Panda, D. Pradhan NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs Manuscript Available on arXiv. |
1527 |
W.K. Shih, T.C. Chen, W.L. Hsu An O(n^2 log n) algorithm for the Hamiltonian cycle problem on circular-arc graphs SIAM J. Comput. 21 No.6 1026-1046 (1992) |
1528 |
L. Ibarra A simple algorithm to find Hamiltonian cycles in proper interval graphs Information Proc. Lett. 109 Issue 18 1105-1108 (2009) |
1529 |
J.M. Keil Finding hamiltonian circuits in interval graphs Information Proc. Lett. 20 201-206 (1985) |
1530 |
B.S. Panda, S.K. Das A linear time recognition algorithm for proper interval graphs Information Proc. Lett. 87 153-161 (2003) |
1531 |
A.A. Bertossi Finding hamiltonian circuits in proper interval graphs Information Proc. Lett. 17 97-101 (1983) |
1532 |
G.K. Manacher, T.A. Mankus, C.J. Smith An optimum θ(n log n) algorithm for finding a canonical hamiltonian path and a canonical hamiltonian circuit in a set of intervals Information Proc. Lett. 35 205-211 (1990) |
1533 |
M.S. Krisnamoorthy An NP-hard problem in bipartite graphs SIGACT News 7 26-26 (1976) |
1534 |
R.W. Hung, M.S. Chang Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs Theoret. Comput. Sci. 341 411-440 (2005) |
1535 |
S.Y. Hsieh, C.W. Ho, T.S. Hsu, M.T. Ko The Hamiltonian problem on distance-hereditary graphs Discrete Appl. Math. 153 508-524 (2006) |
1536 |
R.-W. Hung, M.-S. Chang, C.-H. Laio The Hamiltonian cycle problem on circular-arc graphs Proc. of the International MultiConference of Engineers and Computer Scientists IMECS 2009 |
1537 |
A. Itai, C. H. Papadimitriou, J. L. Szwarcfiter Hamiltonian paths in grid graphs SIAM J. Comput. Vol.11 No.4 676-686 (1982) |
1538 |
C. Umans, W. Lenhart Hamiltonian cycles in solid grid graphs Proc. of Foundations in Comp. Sci. FOCS 1997 496-505 (1997) |
1539 |
M.R. Garey, D.S. Johnson, R.E. Tarjan The planar Hamiltonian circuit problem is NP-complete SIAM J. Comput. Vol.5 704-714 (1976) |
1540 |
V.I. Benediktovich, V.I. Sarvanov Hamiltonian cycle problem for planar cubic graphs Doklady of the academy of sciences of Belarus No.1 34-37 (1997) |
1541 |
Hamiltonian cycle is NP-complete for locally connected graphs. Add a universal vertex u to a graph G. G has a Hamiltonian
path if and only if G+u has a Hamiltonian cycle. =>: G has a Hamiltonian path with starting vertex s and ending vertex e. Thus, (s, ..., e, u, s) is a Hamiltonian cycle in G+u. <=: G+u has a Hamiltonian cycle. Therefore u has two neighbours s and e in the cycle. Thus (s, ..., e) is a Hamiltonian path in G. (Communicated by Arne Leitert, Pavel Irzhavski) |
1542 |
H. Sachs Über selbstkomplementäre Graphen Publ. Math. Debrecen 9 270-288 (1962) |
1543 |
G.B. Mertzios, I. Bezakova Computing and counting longest paths on circular-arc graphs in polynomial time Discrete Appl. Math, in press doi 10.1016/j.dam.2012.08.024 |
1544 | It is well known that the tree-width of a chordal graph is one less than its maximal clique. It is also well known that a planer graph can not have any clique of size 5 or greater, hence chordal \cap planar has treewidth at most 3 (Communicated by Vatshelle) |
1545 |
A. Asinowski, E. Cohen, M.C. Golumbic, V. Limouzy, M. Lipshteyn, M. Stern Vertex intersection graphs of paths on a grid Journal of Graph Algorithms and Applications Vol.16 No.2 129-150 (2012) |
1546 |
M. Middendorf, F. Pfeiffer The max clique problem in classes of string-graphs Discrete Math. 108 365-372 (1992) |
1547 |
K. Appel, W. Haken Every planar map is four colorable Part I. Discharging Illinois J. of Math. 21 429-490 (1977) |
1548 |
K. Appel, W. Haken Every planar map is four colorable Part II. Reducibility Illinois J. of Math. 21 491-567 (1977) |
1549 |
K. Appel, W. Haken Every planar map is four-colorable American Mathematical Society (1989) |
1550 |
F. Gurski Characterizations for co-graphs defined by restricted NLC-width or clique-width operations Discrete Math. 306 No.2 271-277 (2006) doi 10.1016/j.disc.2005.11.014 |
1551 | D. Eppstein described this class in an answer to a question of Y. Cao. |
1552 |
A. Butman, D. Hermelin, M. Lewenstein, D. Rawitz Optimization problems in multiple-interval graphs Proc. of 17th annual ACM-SIAM symposium on Discrete algorithms SODA2007 268-277 (2007) |
1553 |
M.C. Francis, D. Goncalves, P. Ochem The maximum clique problem in multiple interval graphs Proceedings of WG 2012, Lecture Notes in Computer Science 7551, 57-68 (2012) |
1554 |
F. Koenig Sorting with objectives Ph.D. thesis, Technische Universitaet Berlin (2009) |
1555 |
V.S. Gordon, Y.L. Orlovich, C.N. Potts, V.A. Strusevich Hamiltonian properties of locally connected graphs with bounded vertex degree Discrete Appl. Math. 159 1759-1774 (2011) |
1556 |
G. Chartrand, R. Pippert Locally connected graphs Casopis Pest. M at. 99 158-163 (1974) |
1557 |
A. Abueida, R. Sritharan Cycle extendability and hamiltonian cycles in chordal graph classes SIAM J. Discrete Math. 20 669-681 (2006) |
1558 |
T. Jiang Planar Hamiltonian chordal graphs are cycle extendable Discrete Math. 257 441-444 (2002) |
1559 |
G.R.T. Hendry Extending cycles in graphs Discrete Math. 85 59-72 (1990) |
1560 |
C. Picouleau Complexity of the Hamiltonian cycle in regular graph problem Theoret. Comput. Sci. 131 463-473 (1994) doi 10.1016/0304-3975(94)90185-6 |
1561 |
D. Tankus, M. Tarsi The structure of well-covered graphs and the complexity of their recognition problems J. Combin. Th. Series B 69 No.2 230-233 (1997) doi 10.1006/jctb.1996.1742 |
1562 |
D. Tankus, M. Tarsi Well-covered claw-free graphs J. Combin. Th. Series B 66 No.2 293-302 (1996) doi 10.1006/jctb.1996.0022 |
1563 |
M. Lesk, M.D. Plummer, W.R. Pulleyblank Equi-matchable graphs Graph theory and combinatorics (Cambridge, 1983), 239–254, Academic Press, London, 1984 |
1564 |
M.D. Plummer Well-covered graphs: A survey Quaestiones Math. 16 No.3 253-287 |
1565 |
E.M. Arkin, S.P. Fekete, K. Islam, H. Meijer, J.S.B. Mitchell, Y. Nunez-Rodriguez, V. Polishchuk, D. Rappaport, H. Xiao A study of grid hamiltonicity: Not being (super)thin or solid is hard Computational Geometry: Theory and Applications 42 No.6-7 582-605 (2009) |
1566 |
V.S. Gordon, Y.L. Orlovich, F. Werner Hamiltonian properties of triangular grid graphs Discrete Math. 308 6166-6188 (2008) |
1567 |
D.J. Oberly, S.K. Simic, D.P. Sumner Every connected, locally connected nontrivial graph with no induced claw is hamiltonian J. Graph Th. Vol.3 No.4 351-356 (1979) |
1568 |
J.R. Reay, T. Zamfirescu Hamiltonian cycles in T-graphs Discrete Comput. Geom. 24 497-502 (2000) |
1569 |
Yu.L. Orlovich On locally connected graphs whose maximal vertex degree is at most four Vestsi Nats. Akad. Navuk Belarusi. Ser. Fiz.-Mat. Navuk No.3 97-100 (1999) |
1570 |
Z. Ryjacek Almost claw-free graphs J. Graph Theory 18 No.5 469-477 (1994) doi 10.1002/jgt.3190180505 |
1571 |
M. de Berg, O. Cheong, M. van Kreveld, M. Overmars Computation geometry: Algorithms and applications Springer Verlag (2008) |
1572 |
T. Hiroshima, Y. Miyamoto, K. Sugihara Computation geometry: Algorithms and applications IEICE Trans. Fundamentals Vol. E83 A, No.4 627-638 (2000) |
1573 |
D.E. Taylor, R. Levingston Distance-regular graphs Proceedings of the International Conference on Combinatorial Theory, Lecture Notes in Mathematics 686, 313–323 (1978) |
1574 |
P. Festa, P.M. Pardalos, M.G.C. Resende Feedback set problems in: D.Z. Du, P.M. Pardalos, Handbook of Combinatorial Optimization, Supplement vol. A, Kluwer Academic Publishers, 209-259 (2000) |
1575 |
A. Brandstaedt On improved time bounds for permutation graph problems Intern. Workshop on Graph--Theoretic Concepts in Comp. Sci. 1993, Lecture Notes in Comp. Sci. 657 1-10 (1993) |
1576 |
Y.D. Liang On the feedback vertex set problem in permutation graphs Information Proc. Lett. 52 123-129 (1994) doi 10.1016/0020-0190(94)00133-2 |
1577 |
C.L. Lu, C.Y. Tang A linear-time algorithm for the weighted feedback vertex problem on interval graphs Information Proc. Lett. 61 107-111 (1997) |
1578 |
S.R. Coorg, C.P. Rangan Feedback vertex set on cocomparability graphs Networks 26 101-111 (1995) |
1579 |
M.S Chang, Y.D. Liang Minimum feedback vertex set in cocomparability graphs and convex bipartite graphs Acta Informatica 34 337-346 (1997) |
1580 |
C. Wang, T. Liu, W. Jian, K. Xu Feedback vertex set on tree convex bipartite graphs Proceedings of COCOA 2012 LNCS 7402 95-102 (2012) |
1581 |
Feedback vertex set on AT-free graphs D. Kratsch, H. Mueller, I. Todinca Discrete Appl. Math. 156 No. 10 1936-1947 (2008) doi 10.1016/j.dam.2007.10.006 |
1582 |
B. Courcelle, S. Oum Vertex-minors, monadic second-order logic and a conjecture by Seese J. Comb. Theory (B) 97 91-126 (2007) |
1583 |
T. Kloks, C.-H. Liu, S.-H. Poon Feedback vertex set on chordal bipartite graphs Manuscript (2012) Available on arXiv. |
1584 |
A. Takaoka, S. Tayu, S. Ueno On minimum feedback vertex set in graphs Third Internation Conference on Networking and Computing 429-434 (2012) doi 10.1109/ICNC.2012.81 |
1585 |
F. Gavril Minimum weight feedback vertex sets in circle graphs Information Proc. Lett. 107 No.1 1-6 (2008) doi 10.1016/j.ipl.2007.12.003 |
1586 |
S. Ueno, Y. Kajitani, S. Gotoh On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three Discrete Math. 72 No.1-3 355-360 (1988) doi 10.1016/0012-365X(88)90226-9 |
1587 |
D. Li, Y. Liu, A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph Acta Math. Sci. (English Ed.) 19 (1999), no. 4, 375–381 |
1588 |
The decycling number of graphs S. Bau, L.W. Beineke Australas. J. Comb. 25 285-298 (2002) |
1589 |
R.M. Karp Reducibility among combinatorial problems Complexity of Computer Computations (R.E. Miller, J.W. Thatcher, ed.), Plenum Press, New York-London 85-103 (1972) |
1590 |
W. Jiang, T. Liu, T. Ren, K. Xu Two hardness results on feedback vertex sets Frontiers in Algorithmics and Algorithmic Aspects in Information and Management; Lecture Notes in Computer Science 6681 233-243 (2011) |
1591 |
W. Jiang, T. Liu, K. Xu Tractable feedback vertex sets in restricted bipartite graphs Proceedings of COCOA 2011 Lecture Notes in Computer Science 6831, 424-434 (2011) |
1592 |
E. Speckenmeyer On feedback vertex sets and nonseparating independent sets in cubic graphs J. of Graph Theory 12 No.3 405-412 (1988) doi 10.1002/jgt.3190120311 |
1593 | Feedback vertex set is NP-complete for planar graph of maximum degree 4. By subdividing each edge by one new vertex, it easily follows that feedback vertex set is also NP-complete on bipartite planar graphs of maximum degree 4 (V.B. Le). |
1594 |
J.M. Keil, L. Stewart Approximating the minimum cover and other hard problems in subtree filament graphs Discrete Appl. Math. 154 1983-1995 (2006) |
1595 |
F. Gavril Minimum weight feedback vertex sets in circle n-gon graphs and circle trapezoid graph Discrete Math. Algorithm. Appl. 3, 323-336 (2011) doi 10.1142/S1793830911001243 |
1596 |
Y.-L. Lin Circular and circle trapezoid graphs J. Sci. Eng. Tech. 2 11-17 (2006) |
1597 |
D. Kratsch, T. Kloks, H. Mueller Measuring the vulnerability for classes of intersection graphs Discrete Appl. Math. 77 259-270 (1997) |
1598 |
M.M. Halldorson, S. Kitaev, A. Pyatkin Alternation graphs Proceedings of WG 2011, Lecture Notes in Computer Science 6986, 191-202 (2011) |
1599 |
S. Kitaev, A. Pyatkin On representable graphs Automata, languages and Combinatorics 13 No.1 45-54 (2008) |